package greedy

import (
	"math"
	"traning/algorithm/muxicode_learning_map/part_one/data_struct/heap/base"
)

func GetLessMoney(splits []int) int {
	if len(splits) == 0 {
		return 0
	}
	return GetLessMoneyProcess(splits, 0)
}

func GetLessMoneyProcess(splits []int, pre int) int {
	if len(splits) == 1 {
		return splits[0]
	}
	ans := math.MaxInt64
	for i:=0; i<len(splits); i++ {
		for j:=i+1; j<len(splits); j++ {
			ans = min(ans, GetLessMoneyProcess(CopyAndMerge(splits, i, j), pre+splits[i]+splits[j]))
		}
	}
	return ans
}

func CopyAndMerge(splits []int, i, j int) []int {
	newAns := make([]int, len(splits)-1)
	curIndex := 0
	for x:=0; x<len(splits); x++ {
		if x != i && x != j {
			newAns[curIndex] = splits[x]
			curIndex++
		}
	}
	newAns[curIndex] = splits[i] + splits[j]
	return newAns
}

func GetLessMoney1(splits []int) int {
	sheap := base.NewSmallHeap(len(splits))
	for _, v := range splits {
		sheap.Push(v)
	}
	for sheap.Size() > 1 {
		cost := sheap.Pop() + sheap.Pop()
		sheap.Push(cost)
	}
	return sheap.Pop()
}